/*
 * @lc app=leetcode.cn id=84 lang=java
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start

import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        int len = heights.length;
        if(len == 0) return 0;
        
        // 暴力解法----超时
        // int res = 0;
        // for(int i = 0; i<len; i++) {
        //     int left = i, right = i;

        //     int curHeight = heights[i];

        //     while(left > 0 && heights[left-1] >= curHeight) {
        //         left--;
        //     }
        //     while(right < len-1 && heights[right+1] >= curHeight) {
        //         right++;
        //     }

        //     int width = right - left + 1;
        //     res = Math.max(res, width * curHeight);
        // }


        // 单调栈
        Deque<Integer> stack = new LinkedList<>();
        int res = 0;
        stack.push(-1);
        for(int i = 0; i<len; i++) {
            while(stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int curHeight = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                res = Math.max(res, width * curHeight);
            }
            stack.push(i);
        }

        while(stack.peek() != -1) {
            int curHeight = heights[stack.pop()];
            int width = len - stack.peek() - 1;
            res = Math.max(res, width * curHeight);
        }

        return res;
    }
}
// @lc code=end

